// https://leetcode.cn/problems/gas-station/
// Created by ade on 2022/7/26.
//
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
    // 暴力法 超时
    int canCompleteCircuit1(vector<int> &gas, vector<int> &cost) {
        int gasSum = 0, costSum = 0;
        int len = gas.size();
        vector<int> starts = {};
        for (int i = 0; i < len; i++) {
            if (gas[i] >= cost[i]) {
                starts.push_back(i);
            }
            gasSum += gas[i];
            costSum += cost[i];
        }
        if (gasSum < costSum) return -1;
        for (int i = 0; i < starts.size(); i++) {
            gasSum = 0;
            costSum = 0;
            for (int j = starts[i]; j < starts[i] + len; j++) {
                gasSum += gas[j % len];
                costSum += cost[j % len];
                if (gasSum < costSum) break;
            }
            if (gasSum >= costSum) return starts[i];
        }
        return -1;
    }

    // 每次失败之后起点就是失败之后的那个节点
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        // 3, 1, -6, -1, 5, -1
        int len = gas.size();
        for (int i = 0; i < len; i++) {
            int gasSum = 0;
            int costSum = 0;
            for (int j = i; j < i + len; j++) {
                gasSum += gas[j % len];
                costSum += cost[j % len];
                if (gasSum < costSum) {
                    i = j;
                    break;
                };
            }
            if (gasSum >= costSum) return i;
        }
        return -1;
    }
};

int main() {
    Solution so;
    vector<int> gas = {2, 3, 4};
    vector<int> cost = {3, 4, 3};
    int i = so.canCompleteCircuit(gas, cost);
    cout << i << endl;
    return 0;
}